package cn.mengfly.algorithm;


import cn.mengfly.algorithm.collection.stack.LinkedStack;
import cn.mengfly.algorithm.collection.stack.Stack;

import java.util.Arrays;
import java.util.List;

/**
 * 表达式计算(以空格分隔的表达式)
 *
 * @author wangp
 */
public class ExpressionEvaluate {

    private static final List<String> OPS_ARR = Arrays.asList("+", "-", "*", "/", "sqrt");

    private final Stack<String> ops;
    private final Stack<Double> vals;
    private final String[] expression;


    public ExpressionEvaluate(String expression) {
        this.expression = expression.split(" ");
        this.ops = new LinkedStack<>();
        this.vals = new LinkedStack<>();

    }

    private boolean isOps(String str) {
        return OPS_ARR.contains(str);
    }


    public double eval() {
        ops.clear();
        vals.clear();
        for (String expr : expression) {
            if ("(".equals(expr)) {
                continue;
            }
            if (isOps(expr)) {
                ops.push(expr);
                continue;
            }
            if (")".equals(expr)) {
                doOnceEvaluate(ops, vals);
                continue;
            }

            vals.push(Double.parseDouble(expr));
        }
        while (!ops.isEmpty()) {
            doOnceEvaluate(ops, vals);
        }
        return vals.pop();
    }

    /**
     * 修复表达式左括号缺失问题
     *
     * @return 修复后的表达式
     */
    public String fixExpression() {
        Stack<String> subExpression = new LinkedStack<>();
        this.ops.clear();
        for (String expr : expression) {
            if ("(".equals(expr)) {
                continue;
            }
            if (isOps(expr)) {
                ops.push(expr);
                continue;
            }
            if (")".equals(expr)) {
                concatExpression(subExpression);
                continue;
            }
            subExpression.push(expr);
        }

        while (!ops.isEmpty()) {
            concatExpression(subExpression);
        }
        return subExpression.pop();
    }

    private void concatExpression(Stack<String> subExpression) {
        final String op = ops.pop();
        final String exp1 = subExpression.pop();
        final String exp2 = subExpression.pop();
        subExpression.push(String.format("( %s %s %s )", exp2, op, exp1));
    }

    public void doOnceEvaluate(Stack<String> opStack, Stack<Double> valStack) {

        if (opStack.isEmpty()) {
            return;
        }

        final String op = opStack.pop();
        Double val = valStack.pop();
        switch (op) {
            case "+":
                vals.push(vals.pop() + val);
                break;
            case "-":
                Double pop = vals.pop();
                if (pop == null) {
                    pop = 0.;
                }
                vals.push(pop - val);
                break;
            case "*":
                vals.push(val * vals.pop());
                break;
            case "/":
                vals.push(vals.pop() / val);
                break;
            case "sqrt":
                vals.push(Math.sqrt(val));
                break;
            default:

        }
    }

}
